5493. Just Add it

For two given integers n and k find the value of

(Z_n + Z_n-1 – 2Z_n-2) mod 10000007,

where Z_n = S_n + P_n, S_n = 1^k + 2^k + 3^k + ….. + n^k and P_n = 1¹ + 2² + 3³ + …… + nⁿ.

Input. There are several test cases. Each case is a separate line that contains two positive integers n and k (1 < n < 2 * 10⁸, 0 < k < 10⁶). The last test case contains two zeros and should not be processed.

Output. For each test case print the required value in a separate line.

Sample input	Sample output
10 3 9 31 83 17 5 2 0 0	4835897 2118762 2285275 3694

SOLUTION

mathematics + recursion

Algorithm analysis

Let’s simplify the required expression:

Z_n + Z_n-1 – 2Z_n-2 = S_n + S_n-1 – 2 * S_n-2 + P_n + P_n-1 – 2* P_n-2 =

(1^k + 2^k + 3^k + ….. + n^k) + (1^k + 2^k + 3^k + ….. + (n – 1)^k) –

2*(1^k + 2^k + 3^k + ….. + (n – 2)^k) + (1¹ + 2² + 3³ + …… + nⁿ) +

(1¹ + 2² + 3³ + …… + (n – 1)^n-1) – 2*(1¹ + 2² + 3³ + …… + (n – 2)^n-2) =

= n^k + 2(n – 1)^k + nⁿ + 2(n – 1)^n-1

It remains to calculate the sum of the four terms, taken modulo 10000007.

Algorithm realization

Declare a constant MOD that equals to 10000007.

#define MOD 10000007

Function PowMod returns the value of xⁿ mod MOD .

long long PowMod(long long x, long long n)

{

if (!n) return 1;

if (n & 1) return (x * PowMod((x * x) % MOD, n / 2)) % MOD;

return PowMod((x * x) % MOD, n / 2);

}

The main part of the program. For each pair of numbers n and k calculate the sum n^k + 2(n – 1)^k + nⁿ + 2(n – 1)^n-1 modulo MOD.

while(scanf("%lld %lld",&n,&k), n + k)

{

res = (PowMod(n,k) + 2*PowMod(n-1,k) + PowMod(n,n) +

2*PowMod(n-1,n-1)) % MOD;

printf("%d\n",res);

}

Java realization

import java.util.*;

public class Main

{

private final static long MOD = 10000007;

static long PowMod(long x, long n)

{

if (n == 0) return 1;

if (n % 2 == 1) return (x * PowMod((x * x) % MOD, n / 2)) % MOD;

return PowMod((x * x)% MOD, n / 2);

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

while(true)

{

long n = con.nextLong();

long k = con.nextLong();

if (n + k == 0) break;

long res = (PowMod(n,k) + 2*PowMod(n-1,k) +

PowMod(n,n) + 2*PowMod(n-1,n-1)) % MOD;

System.out.println(res);

}

con.close();

}

}